package dynamic;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.stream.IntStream;

public class Dynamic {
    //    53. 最大子序和 简单
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i - 1] + nums[i] > nums[i] ? nums[i - 1] + nums[i] : nums[i];
            max = max > nums[i] ? max : nums[i];
        }
        return max;
    }

    //    62. 不同路径 中等
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0)
            return 0;
        if (m == 1 && n == 1) {
            return 1;
        }
        int[][] path = new int[m][n];
        for (int i = 1; i < path.length; i++)
            path[i][0] = 1;
        for (int i = 1; i < path[0].length; i++)
            path[0][i] = 1;
        for (int i = 1; i < path.length; i++) {
            for (int j = 1; j < path[i].length; j++) {
                path[i][j] = path[i - 1][j] + path[i][j - 1];
            }
        }
        return path[m - 1][n - 1];
    }

    //    63. 不同路径2 中等
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0)
            return 0;
        if (obstacleGrid.length == 1) {
            for (int i = 0; i < obstacleGrid[0].length; i++)
                if (obstacleGrid[0][i] == 1)
                    return 0;
            return 1;
        }
        if (obstacleGrid[0].length == 1) {
            for (int i = 0; i < obstacleGrid.length; i++)
                if (obstacleGrid[i][0] == 1)
                    return 0;
            return 1;
        }
        int[][] path = new int[obstacleGrid.length][obstacleGrid[0].length];
        if (obstacleGrid[0][0] == 0)
            path[0][0] = 1;
        for (int i = 1; i < path.length; i++) {
            if (obstacleGrid[i][0] == 0) {
                path[i][0] = path[i - 1][0];
            } else path[i][0] = 0;
        }


        for (int i = 1; i < path[0].length; i++) {
            if (obstacleGrid[0][i] == 0) {
                path[0][i] = path[0][i - 1];
            } else path[0][i] = 0;
        }

        for (int i = 1; i < path.length; i++) {
            for (int j = 1; j < path[i].length; j++) {
                if (obstacleGrid[i][j] == 0)
                    path[i][j] = path[i - 1][j] + path[i][j - 1];
                else path[i][j] = 0;
            }
        }
        return path[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }

    // 121.买卖股票的最佳时机 easy
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int min = prices[0];
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            min = min > prices[i] ? prices[i] : min;
            result = prices[i] - min > result ? prices[i] - min : result;
        }
        return result;
    }

    //    264. 丑数 II 找出第n个丑数1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
    public int nthUglyNumber(int n) {
        if (n > 1690)
            return 0;
        int[] list = new int[n];
        list[0] = 1;
        int twoIndex = 0;
        int threeIndex = 0;
        int fiveIndex = 0;
        list[0] = 1;
        for (int i = 1; i < n; i++) {
            int ugly = min(list[twoIndex] * 2, list[threeIndex] * 3, list[fiveIndex] * 5);

            if (ugly == list[twoIndex] * 2) {
                twoIndex++;
            }
            if (ugly == list[threeIndex] * 3) {
                threeIndex++;
            }
            if (ugly == list[fiveIndex] * 5) {
                fiveIndex++;
            }
            list[i] = ugly;
        }
        return list[n - 1];
    }

    private int min(int a, int b, int c) {

        int min = a;
        if (b < min) min = b;
        if (c < min) min = c;

        return min;
    }


    //    221. 最大正方形
    public int maximalSquare(int[][] matrix) {
            if (matrix.length == 1 && matrix[0].length == 1)
                return matrix[0][0];
            int[][] result = new int[matrix.length][matrix[0].length];
            int max = 0;
            for (int i = 0; i < result.length; i++) {
                result[i][0] = matrix[i][0];
                max = result[i][0]>max?result[i][0]:max;
            }
            for (int i = 0; i < result[0].length; i++) {
                result[0][i] = matrix[0][i];
                max = result[0][i]>max?result[0][i]:max;
            }
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[i].length; j++) {
                    if (matrix[i][j] == 1) {
                        result[i][j] = min(result[i - 1][j], result[i][j - 1], result[i - 1][j - 1]) + 1;
                        max = result[i][j]>max?result[i][j]:max;
                    }
                }
            }
            return (int)Math.pow(max,2);
    }
    public int minPathSum(int[][] grid) {
        for(int i =1;i<grid[0].length;i++){
            grid[0][i] = grid[0][i-1]+grid[0][i];
        }
        for(int i =1;i<grid.length;i++){
            grid[i][0] = grid[i-1][0]+grid[i][0];
        }
        for(int i =1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
                grid[i][j] =Math.min(grid[i-1][j],grid[i][j-1]) +grid[i][j];
            }
        }
        System.out.println(grid[grid.length-1][grid[0].length-1]);
        return grid[grid.length-1][grid[0].length-1];
    }
}
